package com.example.algorithms;

import java.util.Random;

/**
 * 冒泡排序
 * Created by Geekkiller on 2017/10/21.
 */
public class BubbleSort {

    /**
     * 何为冒泡排序？
     * 冒泡排序是一种交换排序，其原理是 从后向前依次的比较相邻两个数的大小，遍历一次后，
     * 把数组中第i小的数放在第i个位置上
     */

    public void bubbblrSort(int[] list) {
        int temp = 0; //用来交换临时数
        //要遍历的次数
        for (int i = 0; i < list.length; i++) {
            // 从后向前依次的比较相邻两个数的大小，遍历一次后，
            // 把数组中第i小的数放在第i个位置上
            for (int j = list.length - 1; j > i; j--) {
                // 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
                if (list[j - 1] > list[j]) {
                    temp = list[j - 1];
                    list[j - 1] = list[j];
                    list[j] = temp;
                }
            }
            System.out.format("第 %d 趟：\t", i);
            printAll(list);
        }
    }


    /**
     * 对冒泡排序的优化： 当遇到一组之后都没有交换说明已经排好序了
     *
     * @param list
     */
    public void bubbleSort2(int[] list) {

        int temp = 0;
        boolean bChange = false;  //交换标志

        //要遍历的次数
        for (int i = 0; i < list.length; i++) {
            // 从后向前依次的比较相邻两个数的大小，遍历一次后，
            // 把数组中第i小的数放在第i个位置上
            for (int j = list.length - 1; j > i; j--) {
                // 从后向前依次的比较相邻两个数的大小，遍历一次后，把数组中第i小的数放在第i个位置上
                if (list[j - 1] > list[j]) {
                    temp = list[j - 1];
                    list[j - 1] = list[j];
                    list[j] = temp;
                    bChange = true;
                }
            }
            //标志为false 说明没有交换；排序结束。已经是有序数列
            if (!bChange) {
                break;
            }
            System.out.format("第 %d 趟：\t", i);
            printAll(list);
        }
    }

    private void printAll(int[] list) {
        for (int value : list) {
            System.out.print(value + "\t");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        //生成一个随机数组
        final int MAX_SIZE = 10;
        int[] array = new int[MAX_SIZE];
        Random random = new Random();
        for (int i = 0; i < MAX_SIZE; i++) {
            array[i] = random.nextInt(MAX_SIZE);
        }

        //调用冒泡排序方法：
        BubbleSort bubble = new BubbleSort();
        System.out.print("排序前：" + "\t");
        bubble.printAll(array);

        bubble.bubbleSort2(array);
        System.out.print("排序后：" + "\t");
        bubble.printAll(array);


    }

}



















